This invention relates to new and useful improvements in the methods of operating general purpose digital computing systems on one or more programs at the same time (multiprogramming). More specifically, the present invention relates to dynamically adjusting both the productivity and the sharing characteristics of the computing system.
Over the last several years, multiprogramming has been widely accepted by the data processing industry. Prior to multiprogramming, computing systems processed programs on a one-at-a-time basis. If a program did not require all of the resources of the computing system, the unused resources were forced to remain idle for the duration of that particular program. An objective of multiprogramming was to significantly increase resource utilization by processing more than one program concurrently, hence, increasing thruput (productivity). This goal of multiprogramming has seldom been realized primarily because the programs that are attempting to process in parallel often require the same resources. At best, the result is a larger, more expensive computing system run in a shared serial manner. Frequently, and worse, the resources the programs are trying to share operate in a less efficient manner when shared. Thus, the effective utilization actually degrades to a level lower than that of one-at-a-time serial processing.
Resource scheduling for the multiprogrammed computing system is very different from the non-multiprogrammed system where the number or resources is always greater than or equal to the individual program's requirements. In the multiprogrammed system, the situation normally exists where there is an insufficient number of separate physical resources to satisfy the needs of all of the programs being multiprogrammed. This being the case, it becomes necessary to regulate the resource access of the various programs within the system.
There are three basic prior art techniques for regulating resource access. The first is fixed system priority; the second is manual priority; and the third is internal program controlled priority.
Fixed system priority is normally associated with some physical characteristic of the computing system. Different priority levels may be built into the CPU itself. Process control computers are frequently made this way. Certain multiprogramming operating systems are designed such that physical memory location determines priority within the system. Thus, the programs that reside in the highest storage addresses may have the highest resource priority within the system. In either case, once a program begins execution within the computing system, its resource priority is fixed.
Manual priority simply removes the hardware considerations from assigning program resource priority. Any program can be assigned a priority which is independent of the portion of the computing system in which it operates. As with fixed system priority, once the resource priority assignment is made, it is fixed for the duration of the program's execution.
With internal program controlled priority, any program which is specifically written to take advantage of this characteristic has the ability to change its own priority as it executes.
Recently, the problems of the above-described priority assignment techniques have led to consideration of changing access priorities from time to time to improve thruput. However, in these instances, only the CPU's activity was considered.
Fixed priority and manual priority systems cannot optimize thruput except in special instances. During a time interval when two parallel processing programs require the use of a given resource, the program with the higher priority may so dominate the use of that resource that the lower priority program is locked out. Further, the lower priority program may be locked out even though it only needs a relatively small amount of time on the resource under consideration. Finally, the lower priority program will not be able to use other resources for which it has a relatively large demand because of its need for some time on a dominated resource. Hence, the computing system works on a more or less one-at-a-time basis.
Internal program controlled priority has several drawbacks. The programs themselves must have been specifically written to take advantage of the priority assignment capability in the system. Programs that run CPU-bound on one machine may run very peripheral-bound on another machine. (When a program can saturate, that is, use 100% of a particular resource, it is said to be bound by that resource.) So, for internal program controlled priority to work effectively, it must take into consideration the particular computing system in which it is running. A human failing comes into play also. When the programmer himself has the ability to select his programs' resource priorities, more often than not he will select the very highest priority in the system.
When two or more programs time share a resource with equal resource priority or when two or more programs with different resource priority share a resource because of the inability of the program with highest resource priority to saturate the resource, the resulting alternate use of that peripheral resource may cause the total effective system utilization to be significantly lower than executing one program at a time. This system degradation occurs frequently today in computing systems that utilize disk storage facilities. When the disk is dedicated to one of the programs, it can perform many data transfers without seeking to a new location on the disk. However, when it is shared between two programs, the data transfers are frequently separated by delaying or degrading seeks. The function of mechanically moving the read/write heads to the new disk location is called seeking.
The shortcomings of prior art are tabulated briefly below:
1. There is no analysis of the peripheral resources. PA1 2. There is no priority control of degradable resources. PA1 3. There is no method of regulating a program's access to different resources in the system in an unlike manner. PA1 4. There is no method of taking into consideration program resource contention and selecting a subset of the processing programs that will increase total system resource utilization. PA1 5. There is no method of varying the regulating characteristics with time.